package com.other.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 插入排序：直接插入排序、二分法插入排序、希尔排序
 *
 * @author ymsxyz
 * @version 1.0
 * @date 2021/2/17
 */
public class InsertSort {

    private static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 100, 155, 199, 200, 1000, 1000, 1000, 2000, 3333, 44444, 5555, 66666, 777777};
    private static int[] arr1 = {777777, 66666, 5555, 44444, 3333, 2000, 1000, 1000, 1000, 200, 199, 155, 100, 8, 7, 6, 5, 4, 3, 2, 1};
    private static int[] arr2 = {1000, 1000, 1000, 200, 199, 155, 100, 8, 7, 6, 5, 4, 3, 2, 1, 777777, 66666, 5555, 44444, 3333, 2000};

    public static void main(String[] args) {
        //直接插入排序
        directInsertionSort(arr);
        directInsertionSort(arr1);
        directInsertionSort(arr2);
        Arrays.stream(arr).forEach(System.out::println);
        Arrays.stream(arr1).forEach(System.out::println);
        Arrays.stream(arr2).forEach(System.out::println);
    }

    /**
     * 文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，
     * 故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为
     * O(n2)，这时最坏的情况。
     * <p>
     * 直接插入排序的平均时间复杂度为O(n2)。
     *
     * @param
     * @return void
     */
    //@Test
    public static void directInsertionSort(int[] arr) {
        /*
            步骤:
            外i:1-->n-1
            内j:i-->0
         */
        int var;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                //arr[j]与前面一个元素比较,若小于则换位,然后继续和前一个比较,直到大于或等于前一个元素
                if (arr[j] < arr[j-1]) {
                    var = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = var;
                } else {
                    break;
                }
            }
        }
    }

}